package com.algorithm;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 买卖股票的最佳时机 III
 */
public class BestTimeToBuyAndSellStockIii {

    public static int maxProfit(int[] prices) {
        if (prices.length==0){
            return 0;
        }
        //第一个参数为买入次数 第二个为股票天数
        int dp[] []=new int[3][prices.length];

        for (int i=0;i<prices.length;i++){
            dp[0][i]=0;
        }
        for (int i=0;i<=2;i++){
            dp[i][0]=0;
        }

        for (int i=1;i<3;i++){
            int maxProfit=-prices[0];
            for (int j=1;j<prices.length;j++){
                dp[i][j]=Math.max(dp[i][j-1],prices[j]+maxProfit);
                maxProfit=Math.max(maxProfit,dp[i-1][j]-prices[j]);
            }
        }
        return dp[2][prices.length-1];
    }

    public static void main(String[] args) {
        int [] nums=new int[]{3,3,5,0,0,3,1,4};
        int result = maxProfit(nums);
        System.out.println(result);
    }
}
